package com.gorkr.labuladong.data_struct.linked_list;

import org.junit.jupiter.api.Test;

import java.util.HashMap;

/**
 * @author gorkr
 * @date 2022/08/07 08:51
 **/
public class M138CopyListWithRandomPointer {

    class Node {

        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {

        // 旧节点 映射到 新节点
        HashMap<Node, Node> map = new HashMap<>();
        Node p = head;

        // 复制生成的链表头节点
//        Node qHead = new Node(-99999);
        Node q;
        //遍历原始 链表 复制所有节点
        while (p != null) {
            q = new Node(p.val);
            map.put(p, q);
            p = p.next;
        }

        p = head;
        while (p != null) {
            map.get(p).next = map.get(p.next);
            map.get(p).random = map.get(p.random);
            p = p.next;
        }
        return map.get(head);
    }

    private HashMap<Node, Node> map = new HashMap<>();

    public Node copyRandomList2(Node head) {
        if(head==null){
            return null;
        }

        if(!map.containsKey(head)){
            Node node = new Node(head.val);
            map.put(head,node);
            node.next = copyRandomList2(head.next);
            node.random = copyRandomList2(head.random);
        }
        return map.get(head);
    }


}
    